import common.ListNode;

/**
 * 19. Remove Nth Node From End Of List 删除链表的倒数第 N 个结点
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list
 */
class RemoveNthFromEnd {

    /**
     * 方法：使用双指针，右指针先走n步，然后左右指针一起走，当右指针到达末尾时，左指针的下一个节点就是要删除的节点
     * 
     * Args:
     *   head: 链表头节点
     *   n: 要删除的倒数第n个节点
     * 
     * Returns:
     *   删除倒数第n个节点后的链表头节点
     * 
     * Time: O(N) - 需要遍历一次链表，N为链表长度
     * 
     * Space: O(1) - 只使用了常数个指针变量
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = dummy;
        while(n-- > 0){
            right = right.next; // 右指针先向右走 n 步
        }
        while(right.next != null){
            left = left.next;
            right = right.next;
        }
        // 左指针的下一个节点就是倒数第 n 个节点
        left.next = left.next.next;
        return dummy.next;
    }
}